The present invention relates generally to halftone images and more particularly to methods of generating halftone images by a dither matrix.
A printer can be designed to print a picture as a halftone or a grey scale image. For an halftone image, each pixel of the image either has a symbol printed or not printed. For a grey scale image, each symbol on a pixel is further refined to have one of many grey levels.
A halftone image is usually easier and cheaper to generate than a grey scale image. Many relatively low cost printers are specifically designed to print halftone images. To use such a printer to print a grey scale image, the image must be transformed to a half tone image. One objective of the printing industry is to develop appropriate transformation techniques so that the halftone image becomes visually indistinguishable from the grey scale image.
One prior art method transforms a grey scale image to a halftone image by means of a dither matrix. The grey scale image has many pixels, each pixel having a value. The dither matrix occupies a physical space and has numerous elements, each element also having a value. This matrix is mapped over the grey scale image. For an image that is larger than the space occupied by the dither matrix, the matrix replicates itself to cover the entire image. Each element in the matrix is compared to its corresponding grey scale image pixel. If the grey scale image pixel has a larger value, a symbol will not be printed in a corresponding position of the halftone image.
In order to generate a visually pleasing halftone image using the above method, the dither matrix must be carefully designed. The elements in the matrix should not be generated by a random number generator, because a fully random pattern would create a noisy image corrupting the content of the grey scale image.
One prior art method of designing the matrix is known as the void-and-cluster method. A general discussion of the void-cluster method can be found in "The Void-and-Cluster Method for Dither Array Generation," written by Robert Ulichney, published in the SPIE/IS&T Symposium on Electronic Imaging Science and Technology, San Jose, Calif., February, 1993.
FIG. 1A shows one grey level of a halftone image pattern generated by the prior art void-and-cluster method. The Figure was printed by a 600 dots-per-inch printer. To enhance the image, each symbol is magnified nine times, with the image duplicated 4 times, once along the horizontal direction, and then along the vertical direction. The pattern has repetitions of perceptible shapes, such as S1, S2, S3 and S4, that were not present in the grey scale image. Those shapes, as shown in FIG. 1B, are formed when the halftone image is printed by the printer because the printed symbols distort the image.
If the grey scale image has a certain number of grey levels, there should be the same number of halftone image patterns, with levels of lightness ranging from no symbols printed to a pattern entirely filled with symbols. The patterns should decrease linearly in lightness to create a linear tone reflectance curve. The tone reflectance of an image on a printed medium is defined as the percentage of incident light reflected by the image. A printed medium covered with printed symbols has a low tone reflectance. A linear tone reflectance means, for example, that a ten percent decrease in the level of lightness in the halftone image pattern translates to a ten percent reduction in the amount of light reflected.
FIG. 2 shows a grey ramp of the halftone image created by the prior-art void-and-cluster method. A grey ramp prints all the different levels of lightness, one pattern next to the other, from very light to very dark. In the present case, there are 256 patterns. The patterns are quite dark from the middle levels downwards. This is because the symbol printed by the printer is larger than the pixel size of the image. The overlapped symbols have significantly darkened the image. Thus the desired degree of lightness and the actual perceived one are very different. This creates a very non-linear tone reflectance curve. FIG. 3 shows the tone reflectance curve of the grey ramp. The curve maps the tone reflectance against the level of lightness: the higher the level on the x-axis, the lighter the pattern. Most patterns with low pattern numbers, patterns from the middle levels downwards in FIG. 2, have very low tone reflectance. Thus, the curve is very non-linear.
One prior art method tries to correct for the nonlinearity by modifying the dither matrix after its formation. That method first generates the dither matrix. Then the grey ramp of the halftone image formed by the dither matrix is printed, and its tone reflectance curve is measured to get a figure similar to that shown in FIG. 3. From the tone reflectance curve, the dither matrix is modified. The vertical-axis in FIG. 3 is changed from providing the tone reflectance to a mirror image of the horizontal-axis. As an example, the level number 150 on the horizontal-axis is mapped to the level number 25 on the vertical-axis. The values of the elements in the dither matrix are changed accordingly. This eliminates a number of patterns of the dither matrix to create a substantially linear tone reflectance curve. However, the gaps between levels are very non-linear. This is because many levels on the horizontal-axis are mapped to low number levels on the vertical-axis, and significantly fewer levels are mapped to high number levels. A general discussion of such a method can be found in "Semiautomatic Printer Calibration With Scanners," written by Shiau and Williams, and published in the Journal of Imaging Science and Technology, 36(3), 1992, page 211-219.
Another prior art method tries to correct for the nonlinearity by modelling a printed dot in an error diffusion algorithm. This method analyzes every pixel of the grey scale image, one at a time, to decide if a dot is to be printed in the corresponding pixel of the halftone image. Errors from each pixel are "diffused" to subsequent neighboring pixels. Such pixel-to-pixel calculation requires very intensive computation. Thus, the error diffusion method usually takes much longer time to generate the halftone image than the dither matrix method. Moreover, the error diffusion method is not suitable for vector graphics, where the values of pixels on an image may not be calculated sequentially. A discussion of such a method can be found in "Model-Based Halftoning," written by Thrasyvoulos N. Pappas, and published in the SPIE/IS&T Symposium on Electronic Imaging Science and Technology, San Jose, Calif., March, 1991.
There is still a need for a way to generate a halftone image with a linear tone reflectance from a gray scale image without very intensive computation. Furthermore, it is desirable to minimize any repetitions of perceptible shapes when the image is printed by a printer.